package algocasts;

public class P38_binarySearchIn2DArray {
    public int[] binarySearchIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
            return new int[]{-1, -1};
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int r = mid / n, c = mid % n;
            if (matrix[r][c] > target) high = mid - 1;
            else if (matrix[r][c] < target) low = mid + 1;
            else return new int[]{r, c};
        }
        return new int[]{-1, -1};
    }
}
